Computation of elementary and transcendental mathematical functions such as sine, cosine, logarithms and others is a required function in modern computing systems. These functions may be evaluated for any point in their domain by any of several methods. Best known among these methods are the Taylor series expansion, the Chebyshev series expansion, the CORDIC method and derivatives, Briggs's method for logarithms, Newton's method and polynomial approximation. These methods vary principally in the primitive operations they require, such as addition, multiplication and factorial evaluation, and the number of iterations they require to produce a result of given accuracy. An important consideration of all of these methods is the precision required of the argument and of intermediate computations to preserve accuracy and other valuable properties in the result.
Most popular in integrated circuit implementations for calculators and microprocessors is the CORDIC method. The popularity of this method stems from its need to use only the relatively simple primitive operations of addition and shift operations, its thorough development in the literature, and the wide range of trigonometric and exponential functions which may be evaluated with the method. Especially relevant is the efficiency with which addition and shift operations are implemented using electronic integrated circuit techniques.
The disadvantages of the CORDIC method are: (1) the large number of constants required to achieve a given level of accuracy, usually one for every two bits of precision in the result, (2) the large number of iterations required to produce a result, one for each constant, (3) the large number of primitive operations per iteration, usually three per iteration, and (4) the rapid accumulation of round-off error in the result, usually one unit in the last place per iteration. As a result, for example, the computation of the sine function to 64 bits would require 32 constants, 32 iterations, 96 additional cycles and provide only 59 bites of accuracy in the result.
In contrast to the CORDIC method, the other methods mentioned above are used infrequently in integrated circuit implementations due primarily to the primitive operations required which usually include a multiply as well as an add in each iteration. The consequence of this requirement is that evaluation must proceed very slowly, due to the use of add-shift type multiplies, or considerable circuitry and, therefore, chip surface area must be devoted to the implementation of a fast multiplier. The circuit complexity of the array multiplier is further complicated or, equivalently, the evaluation speed correspondingly reduced by the requirement of these other algorithms to perform full-precision multiplication of the argument by itself or by a constant.
Other disadvantages attendant to the methods other than the CORDIC method include the need for many iterations, slow or non-uniform convergence to the result, oscillatory behavior around the infinitely precise values resulting in non-monotonic behavior of the approximate function, and the requirement for additional primitive operations such as division and factorials. The consequence of these disadvantages is larger circuit size and complexity, slower evaluation of the desired function and degraded accuracy.
Accordingly, a need has arisen for a method of function approximation which requires relatively few iterations to achieve a given level of accuracy, converges quickly and uniformly, accumulates round-off error in a relatively slow manner, and produces monotonic approximations to monotonic functions.